package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/15 12:07
 */

/**
 * 归并排序
 *
 * 时间复杂度：
 * 最好/平均/最坏： O(n * log(n))
 *
 * 空间复杂度：
 * 最好/平均/最坏： O(n)
 *
 * 稳定型：具备稳定性    8
 */
public class MergeSort {
    public static void main(String[] args) {
        long[] array = new long[1000_0000];
        Random random = new Random();
        for (int i = 0; i < 1000_0000; i++) {
            array[i] = random.nextInt();
        }

        long[] copy = Arrays.copyOf(array, array.length);

        mergeSort(array);
        Arrays.sort(copy);

        System.out.println(Arrays.equals(copy, array));
    }

    public static void main1(String[] args) {
        long[] array = {9, 5, 1, 0, 3, 8, 2, 4, 6};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void mergeSort(long[] array) {
        mergeSortInternal(array, 0, array.length);
    }

    // 待排序区间：[from, to)
    private static void mergeSortInternal(long[] array, int from, int to) {
        if (to - from <= 1) {
            return;
        }

        // 把待排序区间对半分开
        // 找到中间位置下标
        int mid = from + (to - from) / 2;
        // 整个区间被切割成
        // [from, mid)
        // [mid, to)
        // 按照相同的方式，先把左右两个区间变得有序
        mergeSortInternal(array, from, mid);
        mergeSortInternal(array, mid, to);

        // [from, mid)   有序了
        // [mid, to)     有序了

        merge(array, from, mid, to);
    }

    private static void merge(long[] array, int from, int mid, int to) {
        int size = to - from;
        // 需要的额外空间
        long[] e = new long[size];
        int eIdx = 0;

        int leftIdx = from; // 左边区间要处理的元素的下标
        int rightIdx = mid; // 右边区间要处理的元素的下标
        // 什么条件表示左边区间 [from, mid) 就没有元素了   leftIdx == mid
        // 同理右边区间：rightIdx == to
        // 两个区间都有元素的时候才要比较
        // 左区间有元素：leftIdx < mid
        // 右: rightIdx < to
        // leftIdx < mid && rightIdx < to
        while (leftIdx < mid && rightIdx < to) {
            // 要比较的两个元素 array[leftIdx] 和 array[rightIdx]
            if (array[leftIdx] <= array[rightIdx]) {
                // 取左边的元素放入 e 数组
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            } else {
                // 取右边的元素放入 e 数组
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }

        // 说明有一个区间的元素被全部取完了
        // 右边取完了，把左边的所有元素依次放到 e 中
        while (leftIdx < mid) {
            e[eIdx] = array[leftIdx];
            eIdx++;
            leftIdx++;
        }
        while (rightIdx < to) {
            e[eIdx] = array[rightIdx];
            eIdx++;
            rightIdx++;
        }


        // e 里是有序的 [0, size)
        // 要把有序的元素从 e 中搬回到 array 中 [from, to)

        for (int i = 0; i < size; i++) {
            array[from + i] = e[i];
        }
    }
}

